#ifndef _COMMUNAL_H_
#define _COMMUNAL_H_

typedef int Rank;

//作为sort的参数用以调用不同的排序算法
typedef enum {
    BUBBLE_SORT,
    INSERTION_SORT,
    SHELL_SORT,
    SELECTION_SORT,
    HEAP_SORT,
    MERGE_SORT_ITERATIVELY,
    MERGE_SORT_RECURSIVELY,
    QUICK_SORT,
    COUNTING_SORT,
    RADIX_SORT
} SortMethod;

//作为search的参数用以调用不同的查找算法
typedef enum {
    BIN_SEARCH,
    FIB_SEARCH
} SearchMethod;

template <typename T>
void swap(T& a, T& b) {
    T temp = a;
    a = b;
    b = temp;
    return;
}

template <typename T>
bool lt(T const* a, T const* b) {
    return lt(*a, *b);
}

template <typename T>
bool lt(T const& a, T const& b) {
    return a < b;
}

template <typename T>
bool eq(T const* a, T const* b) {
    return eq(*a, *b);
}

template <typename T>
bool eq(T const& a, T const& b) {
    return a == b;
}

//多个元素命中时，返回rank最大者，查找失败时返回失败的位置
template <typename T>
Rank binSearch(T* A, T const& e, Rank lo, Rank hi) {
    while (lo < hi) {
        Rank mi = (lo + hi) >> 1;
        (e < A[mi]) ? hi = mi : lo = mi + 1;
    }
    return --lo;
}

//md看不懂
template <typename T>
Rank fibSearch(T* A, T const& e, Rank lo, Rank hi) {
    Fib fib(hi - lo);
    while (lo < hi) {
        while (hi - lo < fib.get())
            fib.prev();
        Rank mi = lo + fib.get() - 1;
        if (e < A[mi])
            hi = mi;
        else if (e > A[mi])
            lo = mi + 1;
        else
            return mi;
    }
    return -1;
}

#endif